package dp;

/**
 *
 */
public class P376 {
    public int wiggleMaxLength(int[] nums) {
        int len = nums.length;
        int[][] dp = new int[len][2];
        dp[0][0] = 1; //正
        dp[0][1] = 1; //负
        for (int i = 1; i < len; i++) {
            int num = nums[i];
            for (int j = 0; j < i; j++) {
                if (num > nums[j]) {
                    dp[i][0] = Math.max(dp[j][1] + 1, dp[i][0]);
                } else if (num < nums[j]) {
                    dp[i][1] = Math.max(dp[j][0] + 1, dp[i][1]);
                } else {
                    dp[i][0] = 1;
                    dp[i][1] = 1;
                }
            }
        }
        int maxLen = 0;
        for (int[] row : dp) {
            maxLen = Math.max(maxLen, Math.max(row[0], row[1]));
        }
        return maxLen;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1, 17, 5, 10, 13, 15, 10, 5, 16, 8};
        int result = new P376().wiggleMaxLength(nums);
        System.out.println(result);
    }
}
